package com.ls.que96_100;

/**
 * @author ：ls
 * @date ：2022/3/14 12:25
 * @description：...
 */
public class IsInterleave {
    public boolean isInterleave(String s1, String s2, String s3) {
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();
        if(s1.length() + s2.length() != s3.length())
            return false;
        if (s1.length()==0)
            return s2.equals(s3);
        if (s2.length()==0)
            return s1.equals(s3);
        boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];
        int i,j;
        dp[1][0] = c1[0] == c3[0];
        dp[0][1] = c2[0] == c3[0];
        for (i=2;i<=c1.length;i++)
            dp[i][0] = c1[i-1] == c3[i-1] && dp[i-1][0];
        for (i=2; i<=c2.length;i++){
            dp[0][i] = c2[i-1] == c3[i-1] && dp[0][i-1];
        }

        for (i=1; i<=c1.length;i++){
            for (j=1;j<=c2.length;j++){
                dp[i][j] = c1[i-1] == c3[i+j-1] && dp[i-1][j] || c2[j-1] == c3[i+j-1] && dp[i][j-1];
            }
        }
        return dp[c1.length][c2.length];
    }
}
